package someTestExcemple.huaweiOd.container.stack;
//华为OD机试 - 阿里巴巴找黄金宝箱(IV) - 栈（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/132052320
import java.util.*;
//todo 单调栈是一种特殊的栈，它内部的元素是单调递增或者单调递减的,也就是栈底元素到栈顶元素对应的数组值是递减的。
//在本题中，使用单调递减栈来实现。
//单调栈的常用应用就是找左/右边，第一个比当前元素大/小的元素/的位置/距离这些
public class GoldChestIV {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入的数字子串
        String input = scanner.nextLine();
        scanner.close();

        // 将输入的字符串按逗号分割成字符串数组
        String[] strs = input.split(",");
        int n = strs.length;
        int[] nums = new int[n];
        // 将字符串数组转换为整数数组
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(strs[i]);
        }

        // 结果数组，用于存储每个位置的元素的下一个更大元素值
        int[] result = new int[n];
        //填充为-1
        Arrays.fill(result, -1);
        // 单调栈，存储数组的索引
        Stack<Integer> stack = new Stack<>();

        //由于是循环数组，需要变动一下单调栈的写法

        // 遍历数组两次，模拟循环数组
        //相当于又把0-n赋值一份放在后面·
        for (int i = 0; i < 2*n; i++) {
            //真实下标，防止数组越界
            int index = i%n;
            int num = nums[index];
            while (!stack.isEmpty() && num > nums[stack.peek()]) {
                // 当栈不为空且当前元素大于栈顶元素
                //就说明找到了第一个大于栈顶元素的值
                result[stack.pop()] = num;
            }
            //只有i<n的时候构建单调栈 -防止重复压栈
            //i>n后只是进行查找，更新结果数组result[]
            if(index <n) {
                stack.push(index);
            }
        }

        // 输出结果
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(result[i]);
            if (i < n - 1) {
                sb.append(",");
            }
        }
        System.out.println(sb.toString());
    }
}
